In a distributed storage system, where the failure of an individual storage component may cause part of the stored data to be lost, replication of the stored data is a common technique used to reduce the impact of any storage component failure. Unfortunately, replication of the stored data comes at the cost of increased storage utilization. For example, making two copies of every stored data item will occupy twice as much storage space.
As an alternative to storing data twice, Reed Solomon error correcting codes (a.k.a., parity blocks) were developed to provide equivalent replication protect at a reduced storage usage cost. By way of example, a one (1) byte Reed Solomon error correcting code, which can be computed using a lookup table, may be used by software implementing a redundant array of independent disks (RAID) system in an effort to provide data redundancy. However, this solution often comes with a significant performance penalty.